class Solution {
public:
    void dfs(int row)
    {
        if (row >= _n)
        {
            ret.push_back(board);
            return;
        }
        
        //考虑每一行，遍历该行的每一列
        string tmp;
        for (int i = 0; i < _n; i++)
        {
            //如果该列可以放皇后
            if (!used_col[i] && !used_main_diagonal[row - i + _n] && !used_sub_diagonal[row + i])
            {
                string tmp_bak = tmp;
                tmp_bak += 'Q';

                //更新棋盘状态
                used_col[i] = true;
                used_main_diagonal[row - i + _n] = true;
                used_sub_diagonal[row + i] = true;

                tmp_bak += string(_n - i - 1, '.');
                board.push_back(tmp_bak);   //将这一行的放置情况记录到棋盘中

                dfs(row + 1);   //分析下一行
                board.pop_back();

                //退出后恢复棋盘状态，并将放置皇后的地方改为空位
                used_col[i] = false;
                used_main_diagonal[row - i + _n] = false;
                used_sub_diagonal[row + i] = false;
                tmp += '.';
            }
            else
                tmp += '.';
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        _n = n;
        dfs(0); 

        return ret;
    }
private:
    vector<vector<string>> ret; //记录返回值
    vector<string> board;   //记录每一种可能的棋盘  
    bool used_col[9] = {false}; //用于记录每列是否存在皇后
    bool used_main_diagonal[2*9] = {false}; //用于记录每个主对角线是否存在皇后
    bool used_sub_diagonal[2*9] = {false};  //用于记录每个副对角线是否存在皇后
    int _n;
};
